/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/median-of-two-sorted-arrays
   @Language: C++
   @Datetime: 19-04-15 15:51
   */

// Method 1, merge, Time O(m+n), Space O(1), Time 435ms
class Solution {
public:
	/*
	 * @param A: An integer array
	 * @param B: An integer array
	 * @return: a double whose format is *.5 or *.0
	 */
	double findMedianSortedArrays(vector<int>& A, vector<int>& B) {
		int m=A.size(), n=B.size();
		int ab[2]={0,0};
		for(int i=0, j=0, k=0; (i<m || j<n) && k<=(m+n)/2; ++k){
			swap(ab[0],ab[1]);
			if(i>=m) ab[1]=B[j++];
			else if(j>=n) ab[1]=A[i++];
			else ab[1]=A[i]<B[j]?A[i++]:B[j++];
		}
		if((m+n)&1) return ab[1];
		else return (ab[0]+ab[1])/2.0;
	}
};


// Method 2, Time O(log(m+n)), Space O(1), Time 297ms
class Solution {
public:
	/*
	 * @param A: An integer array
	 * @param B: An integer array
	 * @return: a double whose format is *.5 or *.0
	 */
	double findMedianSortedArrays(vector<int> &A, vector<int> &B) {
		// write your code here
		if(A.size()>B.size()) return findMedianSortedArrays(B,A);
		int m=A.size(), n=B.size();
		for(int left=0, right=m; left<=right;){
			int i=(left+right)/2;
			int j=(m+n+1)/2-i;
			if(i<right && B[j-1]>A[i]) left=i+1;
			else if(i>left && A[i-1]>B[j]) right=i-1;
			else{
				int maxl=0;
				if(i==0) maxl=B[j-1];
				else if (j==0) maxl=A[i-1];
				else maxl=max(A[i-1],B[j-1]);
				if((m+n)%2) return maxl;
				int minr=0;
				if(i==m) minr=B[j];
				else if(j==n) minr=A[i];
				else minr=min(A[i],B[j]);
				return (maxl+minr)/2.0;
			}
		}
		return 0;
	}
};
